#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int n,k,a[N];
vector<int> vec[N];
vector<pair<int,int>> vec2[N];
struct node{
	int mn,cnt,tag;
}t[N<<2];
#define ls (k<<1)
#define rs (k<<1|1)
inline void pushup(int k)
{
	t[k].mn = min(t[ls].mn,t[rs].mn);
	t[k].cnt = 0;
	if(t[k].mn==t[ls].mn) t[k].cnt+=t[ls].cnt;
	if(t[k].mn==t[rs].mn) t[k].cnt+=t[rs].cnt;
}
inline void add(int k,int v){t[k].mn+=v,t[k].tag+=v;}
inline void down(int k)
{
	if(t[k].tag)
	{
		add(ls,t[k].tag),add(rs,t[k].tag);
		t[k].tag = 0;
	}
}
void build(int k,int l,int r)
{
	t[k].mn = t[k].tag = 0;
	if(l==r) return t[k].cnt = 1,void();
	int mid = (l+r)/2;
	build(ls,l,mid),build(rs,mid+1,r);
	pushup(k);
}
void change(int k,int l,int r,int x,int y,int v)
{
	if(l>y||r<x) return;
	if(l>=x&&r<=y) return add(k,v);
	int mid = (l+r)/2;
	down(k);
	change(ls,l,mid,x,y,v),change(rs,mid+1,r,x,y,v);
	pushup(k);
}
signed main()
{
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n>>k;
	for(int i = 1;i<=n;i++) vec[i].push_back(0);
	for(int i = 1;i<=n;i++)
		cin>>a[i],vec[a[i]].push_back(i);
	for(int i = 1;i<=n;i++) vec[i].push_back(n+1);
	int sum = 0;
	for(int z = 1;z<(1<<k);z++)
	{
//		cout<<z<<':';
//		for(int i = 1;i<=k;i++)
//			if((z>>i-1)&1) cout<<i<<' ';
//		cout<<'\n';
		for(int i = 1;i<=k;i++)
			if((z>>i-1)&1)
			{
				for(int j = 1;j<=n;j++)
				{
//					cout<<"sss"<<j<<' '<<vec[j].size()<<'\n';
					for(int k = i;k<vec[j].size()-1;k++)
					{
//						cout<<j<<":"<<vec[j][k-1]+1<<' '<<vec[j][k-i+1]<<' '<<vec[j][k]<<' '<<vec[j][k+1]-1<<'\n';
						vec2[vec[j][k-i]+1].push_back({vec[j][k],vec[j][k+1]-1}); 
						vec2[vec[j][k-i+1]+1].push_back({-vec[j][k],vec[j][k+1]-1}); 
					}
				}
			}
		int ans = 0;
		build(1,1,n);
		for(int i = 1;i<=n;i++)
		{
			for(auto _:vec2[i])
			{
				int l = _.first,r = _.second,add = 1;
				if(l<0) l = -l,add = -add;
				change(1,1,n,l,r,add);
			}
			vec2[i].clear();
			if(t[1].mn>0) ans+=n;
			else ans+=n-t[1].cnt;
		}
//		cout<<ans<<'\n';
		if(__builtin_popcount(z)&1) sum+=ans;
		else sum-=ans;
	}
	cout<<sum;
	return 0;
}

